package mine.code.question.动态规划;

import org.junit.Test;

/**
 * 三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。
 * 结果可能很大，你需要对结果模1000000007。
 * <p>
 * 示例1:
 * <p>
 * 输入：n = 3
 * 输出：4
 * 说明: 有四种走法
 *
 * @author caijinnan
 * @date 2020/3/18 11:10
 */
public class 三步问题 {

    @Test
    public void run() {
        int n = 76;
        //1111  13 31 112 121 211 22
        System.out.println(waysToStep(n));
    }

    // 易得dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
    public int waysToStep(int n) {
        if (n == 0) {
            return 0;
        }
        long[] stepNumArr;
        if (n >= 3) {
            stepNumArr = new long[n];
        } else {
            stepNumArr = new long[3];
        }
        //初始化
        stepNumArr[0] = 1L;
        stepNumArr[1] = 2L;
        stepNumArr[2] = 4L;
        if (n <= 3) {
            return (int) stepNumArr[n - 1];
        }
        for (int i = 3; i < n; i++) {
            stepNumArr[i] = stepNumArr[i - 1] % 1000000007L + stepNumArr[i - 2] % 1000000007L + stepNumArr[i - 3] % 1000000007L;
        }
        System.out.println(stepNumArr[n - 1]);

        return (int) (stepNumArr[n - 1]%1000000007L);
    }
}